class Solution:
    def nextPermutation(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        # 首先找到分界点
        index=len(nums)-1
        while index>0 and nums[index-1]>=nums[index]:
            index-=1

        left=index-1
        right=len(nums)-1

        # 在分界点及右边的序列中找到第一个大于分界点左边元素的元素，交换位置
        if left>=0:
            while right>0 and nums[right]<=nums[left]:
                right-=1
            nums[left],nums[right]=nums[right],nums[left]

        left=index
        right=len(nums)-1

        while left<right:
            nums[left],nums[right]=nums[right],nums[left]
            left+=1
            right-=1
        return nums

def main():
    nums = [1,3,2]
    sol=Solution()
    res=sol.nextPermutation(nums)
    print(res)

main()